package com.zlk.algorithm.algorithm.dynamicPlan;

import org.junit.Test;

import java.util.Arrays;

/**
 * @program: algorithm
 * @ClassName FibonacciNumber
 * @description:斐波那契数列  0  1  1  2  3  5 8 13  。。。。。
 * F(0) = 0，F(1) = 1
 * F(n) = F(n - 1) + F(n - 2)，其中 n > 1
 * @author: slfang
 * @create: 2024-03-26 18:48
 * @Version 1.0
 **/
public class Code01_FibonacciNumber {

    public int fib(int n) {
        return fib1(n);
    }

    //暴力递归
    private int fib1(int n) {
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        return fib(n-1)+fib(n-2);
    }

    /**
     * 记忆化搜索，也就是缓存，从顶到低的动态规划又叫记忆化搜索
     */
    private int fib2(int n) {
        int[] dp = new int[n];
        Arrays.fill(dp,Integer.MAX_VALUE);
        return f2(n,dp);
    }

    private int f2(int n, int[] dp) {
        if(dp[n]!=Integer.MAX_VALUE){
            return dp[n];
        }
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        int res = f2(n-1,dp)+f2(n-2,dp);
        dp[n] = res;
        return res;
    }


    /**
     * 从底到顶的动态规划
     */
    private int fib3(int n) { //  6  5+4
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    /**
     * 空间优化版本
     * @param n
     * @return
     */
    public static int fib4(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int lastLast = 0, last = 1;
        for (int i = 2, cur; i <= n; i++) {
            cur = lastLast + last;
            lastLast = last;
            last = cur;
        }
        return last;
    }


///////////////////////////////////////////////////////////////////// 练习 ////////////////////////////////////////////////////////////////////////////////////////////////
    /// 0  1  1  2  3  5 8 13

    /**
     * 暴力
     * @param n
     * @return
     */
    public int f1(int n){
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        return f1(n-1)+f1(n-2);
    }


    /**
     * 记忆化搜索
     * @param n
     * @return
     */
    public int f22(int n,int[] dp){
        if(n==0){
            dp[n] = 0;
            return 0;
        }
        if(n==1){
            dp[n]=1;
            return 1;
        }
        if(dp[n]!=-1){
            return dp[n];
        }
        int i = f1(n - 1) + f1(n - 2);
        dp[n] = i;
        return i;
    }

    /**
     * 从低到顶的动态规划
     * @param n
     * @return
     */
    public int f3(int n){
        int[] dp = new int[n+1];
        dp[0]=0;
        dp[1]=1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

    @Test
    public void test1(){
        System.out.println(f1(3));
        System.out.println(f1(4));
        System.out.println(f1(5));
        System.out.println(f1(6));


        System.out.println("=========================");
        int[] dp = new int[100];
        Arrays.fill(dp,-1);
        System.out.println(f22(4,dp));
        System.out.println(f22(5,dp));
        System.out.println(f22(6,dp));
        System.out.println(f22(7,dp));
        System.out.println("=========================");

        System.out.println(f3(4));
        System.out.println(f3(5));
        System.out.println(f3(6));
        System.out.println(f3(7));
    }

}
